|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (advisor) ; Paulusma, Daniel (referee) ; Šámal, Robert (referee)
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
|
|
|
Eberhard-Like Theorems
Šimečková, Zuzana ; Šámal, Robert (advisor) ; Fiala, Jiří (referee)
Define sequence (pk) = (p3,p4, . . . ) as numbers of k-sized faces - k-gons - of an embedding of a planar graph. A corollary to Euler's formula for planar graphs states that for cubic graphs ∑ k>=3 (6 − k)pk = 12 holds. Naturally, this leads us to explore the nature of p for which a corresponding cubic planar graph exists. Eberhard proved that if p satisfies the equality above then a cubic planar graph that corresponds to p except for the number of hexagons, exists. DeVos et al. show similar theorem, but instead of hexagon, both pentagons and heptagons can be added. In this thesis, we extend their result by using their proof strategy and designing a program to find graphs needed in such proof. We were able to prove that for every pair r,s ∈ N where s < 6 < r < 14 and r,s are coprime the following theorem holds: for each sequence of nonnegative integers satisfying ∑ k>=3 (6 − k)pk = 12 there are infinitely many cubic planar graphs corresponding to p except for the number of both r-gons and s-gons. 1
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (advisor) ; Fink, Jiří (referee)
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi- gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw- ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NP-complete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NP-complete and the polynomial variants of the problem. 1
|
|
|
Eberhard-Like Theorems
Šimečková, Zuzana ; Šámal, Robert (advisor) ; Fiala, Jiří (referee)
Define sequence (pk) = (p3,p4, . . . ) as numbers of k-sized faces - k-gons - of an embedding of a planar graph. A corollary to Euler's formula for planar graphs states that for cubic graphs ∑ k>=3 (6 − k)pk = 12 holds. Naturally, this leads us to explore the nature of p for which a corresponding cubic planar graph exists. Eberhard proved that if p satisfies the equality above then a cubic planar graph that corresponds to p except for the number of hexagons, exists. DeVos et al. show similar theorem, but instead of hexagon, both pentagons and heptagons can be added. In this thesis, we extend their result by using their proof strategy and designing a program to find graphs needed in such proof. We were able to prove that for every pair r,s ∈ N where s < 6 < r < 14 and r,s are coprime the following theorem holds: for each sequence of nonnegative integers satisfying ∑ k>=3 (6 − k)pk = 12 there are infinitely many cubic planar graphs corresponding to p except for the number of both r-gons and s-gons. 1
|
|
|
Approximation of independence number of planar graphs
Berg, Michal ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee)
The independent set problem is a well-known NP-complete problem, which is NP- complete even for planar graphs. But unlike general graphs, there exists an polynomial- time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomial-time approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (advisor) ; Paulusma, Daniel (referee) ; Šámal, Robert (referee)
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
|
guest ::
